package algorithms.betterqueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @功能
 * @创建时间 2020/12/21
 * 这里是弹出最大值   
 */
public class MaxPQ<Key extends Comparable<Key>> {
    public static void main(String[] args) {
        int[] nums = {1,2,2,3};
        System.err.println(subsetsWithDup(nums));
    }




    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        dfs(nums,0,list);

        return ans;

    }

    private static void dfs(int[] nums,int index,List<Integer> list) {
        if (index >= nums.length) {
            list.clear();
            return;
        }
        list.add(nums[index]);
        List<Integer> list1 = new ArrayList<>(list);
        ans.add(list1);
        if (index>0 && nums[index] == nums[index-1]) {
            list.clear();
            return;
        }

        for (int i = index; i < nums.length; i++) {

            dfs(nums,index,list);


        }
    }
    private Key[]  pq;
    private int N =0;
    public MaxPQ(int maxN){
        pq = (Key[]) new Comparable[maxN+1];
    }
    public   boolean less(int i,int j){
        return pq[i].compareTo(pq[j])<0;
    }
    public  void exch(int i,int j){
        Key t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public Key delMax(){
        Key max=pq[1]; //得到最大元素
        exch(1,N--); //将第一个元素和最后一个元素交换
        pq[N+1] = null; //把最后一个元素值为空，防止对象游离
        sink(1); // 下潜第一个元素，恢复堆的有序性
        return max;

    }
    public void insert(Key v){
        pq[N++] = v;
        swim(N);
    }
    //子节点与父节点的商刚好为2，每次和父节点比较并判断是否交换位置
    private void swim(int k){
        while (k > 1 && less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }
    //找到子节点，判断子节点是否越界，若越界，不进入循环，否则判断其左子节点和右子节点大小，并和大的交换位置，依次循环
    private void sink(int k){
        while (2*k <=N){
            int j = 2*k;
            if(j < N&& less(j,j+1)) j++;
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }

}
